#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;
typedef struct DuLinkedNode{
    ElemType data;//数据域
    struct DuLinkedNode * prior;//指向前驱
    struct DuLinkedNode * next;//指向后继
}DuLinkedNode ,*DuLinkedList;

//基本操作
//插入
void insertDuLinkList(DuLinkedNode * target,ElemType data){
    //新建节点
    DuLinkedNode * newNode = (DuLinkedNode *)malloc(sizeof(DuLinkedNode));
    newNode->data = data;
    //插入模板（讲义）
    DuLinkedNode * preTarget = target->prior;//获取前驱结点
    newNode->prior = preTarget;//step 1:更新插入节点的前驱指针
    newNode->next = target;//step 2:更新插入节点的后继指针
    preTarget->next = newNode;//step 3:更新前驱结点的后继指针
    if(target){
        newNode->next->prior = newNode;//step 4:更新后继节点的前驱指针
    }
}
//删除
void deleteDuLinkList(DuLinkedNode * target){
    //删除模板（讲义）
    target->prior->next = target->next;//更新前驱节点的后继指针
    if(target->next){
        target->next->prior = target->prior;//更新后继节点的前驱指针
    }
    free(target);//释放目标节点
}

//例题30、设计一个算法，将带头双向链表中数据结点的原有顺序保存在每个结点的next域中，
// 而prior域将所有结点按照其值从小到大的顺序链接起来。★★★
/*算法思想：使用插入排序算法对双向链表进行排序。访问双线链表的每一个数据结点，按照从小到大的顺序将其插入
到新表L,并且在插入时通过修改prior指针域来保存其在L中的位置。*/
void order(DuLinkedList list){
    //没看懂题目意思，以下为讲义上的代码
    DuLinkedNode * pDataCur = list->next;//指向第一个数据节点
    list->next = NULL;//构建一个带头节点的空表
    while(NULL != pDataCur){
        DuLinkedNode * pCur = list->prior;//指向排序链表的第一个数据节点
        DuLinkedNode * preCur = list;//指向pCur的前驱
        while(NULL != pCur && pCur->data < pDataCur->data){//寻找插入位置
            preCur = pCur;//更新下一个点的前驱
            pCur = pCur->next;//指向下一个节点
        }//循环结束，preCur指向插入位置
        //插入
        pDataCur->prior = preCur->prior;//更新插入节点的前驱指针
        preCur->prior = pDataCur;//更新前驱节点的前驱指针
        pDataCur = pDataCur->next;//取下一个待插入的数据节点
    }
}
//始终没懂题目意思


// 例题31、设以带头结点得双向循环链表表示得线性表为L=(a1,a2,a3...an)。
// 试写一时间复杂度为O(n)的算法，将L改造为L=(a1,a3,a5...an-1,an...,a4,a2)。★★★★★
void reverseDuLinkedList(DuLinkedList list) {
    // 以下参考讲义
    DuLinkedNode* pCurNode = list->next;     // 当前遍历节点，从链表的第一个节点开始
    list->next = list;                       // 将链表的next指针指向自身，即断开原链表
    list->prior = list;                      // 将链表的prior指针指向自身，即断开原链表
    DuLinkedNode* pTail = list;               // 原链表的尾部指针
    DuLinkedNode* el = (DuLinkedNode*)malloc(sizeof(DuLinkedNode));  // 新链表的头结点
    el->next = el;                           // 将新链表的next指针指向自身
    el->prior = el;                          // 将新链表的prior指针指向自身
    int isEven = 0;                          // 奇偶标志，偶数为1，奇数为0
    while (list != pCurNode) {               // 遍历原链表直到回到头结点
        DuLinkedNode* pNode = pCurNode;      // 当前节点
        pCurNode = pCurNode->next;           // 指向下一个节点
        if (1 == isEven) {
            // 头插法（逆置）
            pNode->next = el->next;          // 将当前节点的next指针指向新链表的第一个节点
            pNode->prior = el;               // 将当前节点的prior指针指向新链表的头结点
            el->next->prior = pNode;         // 新链表的第一个节点的prior指针指向当前节点
            el->next = pNode;                // 新链表的头结点的next指针指向当前节点

            isEven = 0;                      // 切换奇偶标志，由奇数变为偶数
        } else {
            pNode->next = pTail->next;       // 将当前节点插入到原链表的尾部后面
            pNode->prior = pTail;            // 将当前节点的prior指针指向原链表的尾部
            pTail = pNode;                   // 更新原链表的尾部指针
            isEven = 1;                      // 切换奇偶标志，由偶数变为奇数
        }
    }
    // 除去头结点，将剩下的挂到list上
    if (NULL != el->next) {
        pTail->next = el->next;              // 将新链表剩余部分的头节点添加到原链表的尾部
        el->next->prior = pTail;             // 将新链表剩余部分的头节点的prior指针指向原链表的尾部
        el->prior->next = list;              // 将新链表剩余部分的尾节点添加到原链表的头部之后
        list->prior = el->prior;             // 将新链表剩余部分的尾节点的next指针指向原链表的头部
    }
}


int main(){


    return 0;
}
